\chapter{绪论}
正则表达式(Regular expression)具有可以表达难以描述、复杂，但却具备一定规律的
字符串的功能，因此，类似vi、sed、awk、grep等Linux命令都支持正则表达式操作。
除了这些通用工具外，也可以在ANSI C语言中基于不同的正则表达式库实现正则
表达式的编程。

\section{正则表达式}
正则表达式是使用一个字符串来表达\enquote{具有某种特殊规则}的所有字符串的集合。
例如正则表达式\cinline{"fo*"}表示由\cinline{"fo"}、\cinline{"foo"}、%
\cinline{"fooo"}等字符串所构成的字符串集合。如果一个字符串是正则
表达式\cinline{"fo*"}所构成的字符串集合中的一个，则称正则表达式\cinline{"fo*"}%
与字符串s匹配。

正则表达式本质上是一种文本匹配规则，这套规则使用特殊字符来表达匹配逻辑。正则表达式
的核心是理解特殊字符所代表的各种匹配逻辑。关于正则表达式的详细说明，请参阅相关资料。

\section{正则表达式库}

在\cl 中实现正则表达式的编程，可以从低层实现，也可以基于已有的正则表达式第三方库
实现。为避免重复发明轮子，本书选择GNU Regex、 PCRE2、CRE2(Google RE2的C语言封装)和%
Intel Hyperscan 4个开源正则表达式库实现正则表达式的编程。正则表达式库又往往被称为
正则表达式引擎，或简称为正则引擎。

\section{基本概念}

在使用正则表达式库实现正则表达式编程时，需要了解这些库所定义的一些基本概念。

\subsection{模式}

正则表达式往往又称为模式(pattern)，在不引起岐义的情况下，本书中会混合使用这
两种描述方式。

\subsection{语法位和标志位}

在正则表达式库中，为区分不同正则表达式语法及不同的操作模式，这些库都定义了不同
的宏常量，这些宏常量只用1位的0或1来表示不同语法或状态，这些宏常量往往又称为%
\enquote{语法位}或\enquote{标志位}。可以使用\cinline{'|'}按位\enquote{或}运算
实现不同语法位的组合或标志位的组合。

注意，在CRE2库中，语法位的状态是通过称为\enquote{语法对象}的数据结构表示的，
CRE2库为语法对象的设置提供了独立的设置函数。

\subsection{正则缓存}

为了提高速度，在进行正则表达式搜索或匹配之前，往往需要对所用到的正则表达式进行
编译处理。在GNU Regex库和PCRE2库中，编译后的正则表达式又称为正则缓存或匹配模式
缓存。在CRE2库中，编译后的正则表达式又称为正则对象。在Hyperscan库中，编译后的
正则表达式又称为正则数据库。

同样，在不引起歧义的情况下，本书将不区分这些称谓。

\subsection{匹配寄存器}

为记录正则匹配结果，不同的库都提供了用于正则表达式中各个分组(小括号分组)
匹配结果起始位置(包含)和结束位置(不包含)的数据结构。这样的数据结构通称为%
\enquote{匹配寄存器}。

匹配寄存器一般是通过结构体数组或整型数组实现的，同时，PCRE2正则库使用匹配向量
来实现匹配结果的管理，该向量就是数组，其偶数下标元素记录了各分组的匹配起始位置，
寄数下标元素记录了匹配结束位置。

一般情况下，整个正则表达式也是一个分组，记为group 0，在匹配寄存器中，通过下标0
实现引用。

\section{正则库使用流程}
一般来讲，使用正则表达式引擎进行正则表达式编程主要有3个步骤：

\begin{enumerate}
    \item 编译正则表达式
    \item 扫描匹配
    \item 释放资源
\end{enumerate}

可用伪代码描述为：
\begin{codebox}{正则库使用流程}
  设置正则表达式;
  初始化正则缓存;

  do(编译正则表达式);

  if(编译成功)
  {
      do(使用正则缓存在字符串中进行匹配或查找);

      if(匹配或查找成功)
      {
          输出匹配或查找结果;
      }
      else
      {
          报告失败原因;
      }
  }
  else
  {
      报告正则表达式编译错误;
  }

  do(释放资源);
\end{codebox}

当然，针对不同的引擎，其具体操作还会有稍许不同。
对于CRE2库，还可以直接使用正则表达式进行匹配而不需要进行正则表达式的编译，
但这会降低匹配速度。对于Hyperscan库，由于其提供了块扫描、流扫描和向量扫描模式，
因此，其使用流程变化较多，具体可参阅对应\ref{sec-hyperscan-workflow}节的说明。


有关如何时在\cl 中使用第三方库，请参阅笔者撰写的《说C解C》相关章节\cite{cstory2021}。

\section{案例说明}\label{intro-sec-regex-cases}

本书将采用整数范围有效性判断、电话号码有效性判断、整数重复数字判断、找最亲近同学、
比压牌和牌型分类等6个典型应用案例，分别演示采用不同正则表达式库解决实际问题的
策略和方法。

在此，仅对这6个案例的需求和正则表达式设计进行必要说明，有关用正则表达式解决这些
问题的具体代码实现和分析，将在各部分进行详细说明。

\subsection{整数范围有效性判断}

设给定字符串表示一个整数，则可以用正则表达式判断该字符串能否构成指定范围内的
正整数。

例如，可以用\cinline{"^[1-9][0-9]{0,2}$|^1000$"}正则表达式判断是否为$[1, 1000]$%
之间的正整数字符串。

\subsection{电话号码有效性判断}

设某城市电话号码由地区码、前缀、有效号码三部分组成。其中，地区码是0-4位数字；
前缀是以非0开头的3位数字；有效号码是4位数字。各部分之间用减号(-)分隔，若地区码
为空，则前缀之前不包含分隔符。

对于该需求，可以用\cinline{"^(([0-9]{0,4})-)?[1-9][0-9]{2}-[0-9]{4}$"}正则表达式
判断给定的电话号码是否有效。

\subsection{整数重复数字判断}
判断并输出一个正整数中重复出现的数字，如果没有，输出提示信息“No repeated numbers.”，
如果输入不合法，输出“Invalid input”，要求正整数不超过7位。若有多个重复数字，
则按从小到大的顺序输出。

对于一个正整数，可以用\cinline{sprintf()}函数将其输出到字符串中，然后通过正则
表达式\cinline{"([0-9])\\1+"}实现重复数字的判断。

由于CRE2库和Hyperscan库不支持正则表达式分组的反向引用，因此需要构造完整正则
表达式 \cinline{"(0{2,}|1{2,}|2{2,}|3{2,}|4{2,}|5{2,}|6{2,}|7{2,}|8{2,}|9{2,})"} 实现判断。

\subsection{查找最亲近同学}
小明喜欢把他的同学分类，每一类用一个大写英文字母标记。他只愿意亲近一部分类型的
同学。请从小明的同学中挑出他愿意亲近的同学。

给定小明的学号(正整数)，由大写字母组成的字符串表示的小明喜欢的同学类型，
由大写字母组成的字符串表示小明同学（包含他自己）的类型，按照学号有序。学号从1
开始，没有间断和重复。

按照从小到大的顺序依次输出小明喜欢的同学的学号。每个学号之后有一个空格。如果
没有找到小明喜欢的同学，则输出\cinline{"Lonely Xiao Ming"}。

对于该问题，需要根据指定的喜欢类型字符串动态构造正则表达式，然后进行判断，
为判断所有可能，需使用循环调整字符串偏移后进行判断。

\subsection{比压牌}
设只有面值1到9构成的牌，不区分花色。自己手里拿着已经排好序的牌\cinline{in_hand}，
对方出牌的牌是\cinline{op_type}。要求判断手中牌能否能够压过对方出牌。

压牌规则有5种：
\begin{enumerate}
  \item 一张 如4 则5...9可压过
  \item\label{judge-step2} 两张 如44 则55，66，77，...，99可压过
  \item 三张 如444 规则如\ref{judge-step2}
  \item 四张 如4444 规则如\ref{judge-step2}
  \item 五张 牌型只有12345、23456、34567、45678和56789五个，后面的比前面的均大。
\end{enumerate}

如果手里的牌能压过对方出的牌则输出YES 否则NO。

对于该问题，需要根据对方出的牌型在正则表达式查找表中查找指定的正则表达式，
然后进行判断。可用的正则表达式有：

\begin{minipage}{0.90\textwidth}
  \begin{ccode}
    // 正则表达式查找表
    const char *re_pat[] = {
      "(2{1})|(3{1})|(4{1})|(5{1})|(6{1})|(7{1})|(8{1})|(9{1})", // 2--9
      "(2{2})|(3{2})|(4{2})|(5{2})|(6{2})|(7{2})|(8{2})|(9{2})", // 22等
      "(2{3})|(3{3})|(4{3})|(5{3})|(6{3})|(7{3})|(8{3})|(9{3})", // 222等
      "(2{4})|(3{4})|(4{4})|(5{4})|(6{4})|(7{4})|(8{4})|(9{4})", // 2222等
      "(2+3+4+5+6)|" // 23456
      "(3+4+5+6+7)|" // 34567
  \end{ccode}
\end{minipage}

\begin{minipage}{0.90\textwidth}
  \begin{ccode}
      "(4+5+6+7+8)|" // 45678
      "(5+6+7+8+9)"  // 56789
    };
  \end{ccode}
\end{minipage}

\subsection{牌型分类}
设手中的每张牌由花色((S)PADES---黑桃， (H)EARTS---红心， (D)IAMONDS---方块和
(C)LUBS---梅花)和等级(2---9，T, J, Q, K和A)构造，不允许使用王牌，并假定A是
最高等级。请根据手中5张牌的等级和花色将手中的牌分为下列某一类(列出的分类从
最高到最低)\cite{cmodern2013}。

\begin{itemize}
  \item 同花顺(Straight flush，即顺序相连又都是同花色)
  \item 四张(Four of a kind，4张牌等级相同)
  \item 葫芦(Full house，三张加一对)
  \item 同花(Flush，5张牌是同花色的)
  \item 顺子(Straight，5张牌等级顺序相连)
  \item 三张(Three of a kind，3张牌等级相同)
  \item 两对(Two pair，两个对子)
  \item 一对(One pair，2张牌的等级相同)
  \item 其它(High card，任何其他情况的牌)
\end{itemize}

手中的各张牌由等级和花色表示，不区分大小写，如：8caS7Cad3H。

为实现正则匹配，需要先将手中的各张牌的字母转换为大写，这可以用按位异或%
(\cinline{^})运算实现。在转换为大写后，还需要将牌的等级和花色进行分离，
并对等级和花色部分分别进行排序，再用指定的字符(本例中使用\cinline{'#'})%
将它们粘接在一起。最后再交由正则表达式进行匹配判断。

可以通过如下正则表达式实现各类牌型的分类：

\begin{minipage}{0.90\textwidth}
  \begin{ccode}
    // 正则表达式数组
    const char *pat[] = {
      "(2345A|23456|34567|45678|56789|6789T|"
      "789JT|89JQT|9JKQT|AJKQT)#(.)\\2{4}.*", // #0 同花顺
      "(.)\\1{3}.*#.*", // #1 四张
      "((.)\\2{2}(.)\\3{1}#.*|(.)\\4{1}(.)\\5{2}#.*)", // #2 葫芦(三张加一对)
      ".*#(.)\\1{4}.*", // #3 同花
  \end{ccode}
\end{minipage}

\begin{minipage}{0.90\textwidth}
  \begin{ccode}
      "(2345A|23456|34567|45678|56789|6789T|"
      "789JT|89JQT|9JKQT|AJKQT)#.*", // #4 顺子
      "(.)\\1{2}.*#.*", // #5 三张
      "(.)\\1{1}.*(.)\\2{1}.*#.*", // #6 两对
      "(.)\\1{1}.*#.*" // #7 一对
    };
  \end{ccode}
\end{minipage}

同样由于CRE2库和Hyperscan库不支持正则表达式分组的反向引用，因此需要构造完整正则
表达式实现判断，如：

\begin{minipage}{0.90\textwidth}
  \begin{ccode}
    // 正则表达式数组
    const char *pat[] = {
      "(2345A|23456|34567|45678|56789|6789T|"
      "789JT|89JQT|9JKQT|AJKQT)#(S{5}|H{5}|D{5}|C{5})", // #0 同花顺
      "(2{4}|3{4}|4{4}|5{4}|6{4}|7{4}|8{4}|"
      "9{4}|T{4}|J{4}|Q{4}|K{4}|A{4}).*#.*", // #1 四张
      "((2{3}|3{3}|4{3}|5{3}|6{3}|7{3}|8{3}|" // 葫芦
      "9{3}|T{3}|J{3}|Q{3}|K{3}|A{3})(2{2}|3{2}|4{2}|5{2}|6{2}|7{2}|8{2}|"
      "9{2}|T{2}|J{2}|Q{2}|K{2}|A{2}))|"      // 三张加一对
      "((2{2}|3{2}|4{2}|5{2}|6{2}|7{2}|8{2}|9{2}|T{2}|J{2}|Q{2}|K{2}|A{2})"
      "(2{3}|3{3}|4{3}|5{3}|6{3}|7{3}|8{3}|"
      "9{3}|T{3}|J{3}|Q{3}|K{3}|A{3})).*#.*", // 一对加三张
      ".*#(S{5}|H{5}|D{5}|C{5})", // #3 同花
      "(2345A|23456|34567|45678|56789|6789T|"
      "789JT|89JQT|9JKQT|AJKQT)#.*", // #4 顺子
      "(2{3}|3{3}|4{3}|5{3}|6{3}|7{3}|8{3}|"
      "9{3}|T{3}|J{3}|Q{3}|K{3}|A{3}).*#.*", // #5 三张
      "(2{2}|3{2}|4{2}|5{2}|6{2}|7{2}|8{2}|9{2}|T{2}|J{2}|Q{2}|K{2}|A{2}).*"
      "(2{2}|3{2}|4{2}|5{2}|6{2}|7{2}|8{2}|"
      "9{2}|T{2}|J{2}|Q{2}|K{2}|A{2}).*#.*",  // #6 两对
      "(2{2}|3{2}|4{2}|5{2}|6{2}|7{2}|8{2}|"
      "9{2}|T{2}|J{2}|Q{2}|K{2}|A{2}).*#.*"  // #7 一对
    };
  \end{ccode}
\end{minipage}

\begin{note}
  \begin{enumerate}
    \item 本书所有代码仅在Ubuntu 22.04中，用GCC 11.4进行了测试，不能确保在其它
        工具链中能够正确运行；
    \item 本书部分正则表达式示例来自网络，如有侵权，敬请联系删除。
  \end{enumerate}
\end{note}
